# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
def isBadVersion(version):
    d = ([False]*4)
    d.extend([True]*2)
    return d[version]


class Solution:
    def firstBadVersion(self, n):
        start = 0
        end = n
        while start + 1 < end:
            mid = (start + end) // 2
            if mid == 0:
                return 1
            status = isBadVersion(mid)
            if status:
                end = mid
            else:
                start = mid
        return end


if __name__ == '__main__':
    so = Solution()
    m = 5
    r = so.firstBadVersion(m)
    print(r)
